#define _CRT_SECURE_NO_WARNIN
#include"stdio.h"
int PartSort(int* a, int begin, int end)
{
	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		while (begin < end && a[end]>=a[key])
		{
			end--;
		}
		a[hole] = a[end];
		hole = end;

		while (begin < end && a[begin] <= a[key])
		{
			begin++;
		}
		a[hole] = a[begin];
		hole = begin;
	}
	a[hole] = key;
	return hole;

}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}